package org.example.myleet.p407;

import java.util.PriorityQueue;

public class Solution2 {

    /**
     * row, col change
     */
    private static final int[][] DIRECTIONS = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    /**
     * 官方解：使用最小优先堆，堆的比较使用该位置的水面最高海拔，[row, column, height]
     * 原理，最外围的一圈是不能收集雨水的，同时也是整个容器的外围，根据木桶原理，容器内部能装的最多的水取决于最短的板
     * 因此利用最小优先堆不断地获得最短的板，就可以知道容器最多可以装多少水
     * 关于搜索延伸的机制：当最小优先堆弹出最短板的时候，需要观察这个板子四个方向上未访问过的位置（访问过的位置是已经确认的板子）
     * 并以这个最短的板子高度作为可以装水的最大量（新位置的水面最高海拔），并加入堆中，当然，如果相邻的板子比当前最短板还高，那么就按板子的高度入堆
     * 这样做的意义在于，从最短的板子开始寻找新边界，并将新边界高度顺序维护到堆中，则下一个回合时弹出的仍然是探寻到的边界的最短板
     */
    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length, n = heightMap[0].length;
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
        //先把最外围一圈放入堆中
        for (int j = 1; j < n - 1; ++j) {
            pq.offer(new int[]{0, j, heightMap[0][j]});
            visited[0][j] = true;
            pq.offer(new int[]{m - 1, j, heightMap[m - 1][j]});
            visited[m - 1][j] = true;
        }
        for (int i = 0; i < m; ++i) {
            pq.offer(new int[]{i, 0, heightMap[i][0]});
            visited[i][0] = true;
            pq.offer(new int[]{i, n - 1, heightMap[i][n - 1]});
            visited[i][n - 1] = true;
        }
        int water = 0;
        while (!pq.isEmpty()) {
            //弹出当前已知最短板
            int[] p = pq.poll();
            for (int k = 0; k < 4; ++k) {
                //四个方向寻找新边界
                int[] dir = DIRECTIONS[k];
                int neighbourRow = p[0] + dir[0];
                int neighbourCol = p[1] + dir[1];
                if (0 <= neighbourRow && neighbourRow < m && 0 <= neighbourCol && neighbourCol < n && !visited[neighbourRow][neighbourCol]) {
                    //需要新的边界是有效的，一、不越界，二、未访问过
                    if (p[2] > heightMap[neighbourRow][neighbourCol]) {
                        //最短板旁边的柱子高度更低，可以盛水，并且按最短板的高度加入到边界中
                        water += p[2] - heightMap[neighbourRow][neighbourCol];
                        pq.offer(new int[]{neighbourRow, neighbourCol, p[2]});
                    } else {
                        //最短板旁边的柱子高度更高，是新的边界高度，加入到边界中
                        pq.offer(new int[]{neighbourRow, neighbourCol, heightMap[neighbourRow][neighbourCol]});
                    }
                    //标记为已访问
                    visited[neighbourRow][neighbourCol] = true;
                }
            }
        }
        return water;
    }
}
